package com.chapter5.string;

/**
 * 
 * @ClassName: LSD
 * @Description: 低位排序
 * 
 * 时间复杂度是2wN，一般比较类型的排序算法最快都是NlgN。其中w的值是字符串的固定宽度，通常会比较小，所以LSD的时间复杂度依然可以看成是线性级别
 * 
 * @author minjun
 * @date 2015年3月16日 下午10:37:56
 * 
 */
public class LSD {

	/**
	 * 
	 * @Title: sort
	 * @Description: 对字符串数组s的前w的元素进行排序
	 * @param @param s
	 * @param @param w 设定文件
	 * @return void 返回类型
	 * @throws
	 */
	public static void sort(String[] s, int w) {
		int len = s.length;
		int R = 256;
		String[] aux = new String[len];

		for (int i = w - 1; i >= 0; i--) {
			int[] count = new int[R + 1];
			
			// 计数
			for (int j = 0; j < len; j++) {
				count[s[j].charAt(i) + 1]++;
			}
			
			// 索引
			for (int j = 0; j < R; j++) {
				count[j + 1] += count[j];
			}

			// 插入
			for (int j = 0; j < len; j++) {
				aux[count[s[j].charAt(i)]++] = s[j];
			}

			// 复制
			for (int j = 0; j < len; j++) {
				s[j] = aux[j];
			}
		}
	}
}
